#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q,ans[5010][5010],a[5010],b[5010];
void solve_for_ans(int st){
    int nw=0;
    for(int i=1;i<=n;i++)
        b[i]=0;
    for(int i=st;i<=n;i++){
        int nd=a[i]-b[i],kp=1000000000;
        nw+=nd;
        ans[st][i]=nw;
        for(int j=i;j<=i+m-1;j++){
            kp=min(kp,a[j]);
            b[j]=min(kp,b[j]+nd);
            nd=min(nd,a[j]);
        }
    }
    return;
}
signed main(){
    freopen("clear.in","r",stdin);
    freopen("clear.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        solve_for_ans(i);
    for(int i=1;i<=q;i++){
        int x,y;
        cin>>x>>y;
        cout<<ans[x][y]<<"\n";
    }
    return 0;
}
